package com.huangkailong.leetcode;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。<br/>
 * <br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * <br/>
 * 输入：l1 = [1,2,4], l2 = [1,3,4]<br/>
 * 输出：[1,1,2,3,4,4]<br/>
 * 示例 2：<br/>
 * <br/>
 * 输入：l1 = [], l2 = []<br/>
 * 输出：[]<br/>
 * 示例 3：<br/>
 * <br/>
 * 输入：l1 = [], l2 = [0]<br/>
 * 输出：[0]<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * 两个链表的节点数目范围是 [0, 50]<br/>
 * -100 <= Node.val <= 100<br/>
 * l1 和 l2 均按 非递减顺序 排列<br/>
 * <br/>
 *
 * @author huangkl
 * @since 1.0.0
 */
public class MergeTwoLists {


    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }

        ListNode result = new ListNode();
        ListNode tail = result;
        ListNode l1p = l1;
        ListNode l2p = l2;
        while (l1p != null && l2p != null){
            if(l1p.val < l2p.val){
                tail.next = l1p;
                tail = l1p;
                l1p = l1p.next;
            }else if(l1p.val == l2p.val){
                tail.next = l1p;
                tail = l1p;
                l1p = l1p.next;
                tail.next = l2p;
                tail = l2p;
                l2p = l2p.next;
            }else {
                tail.next = l2p;
                tail = l2p;
                l2p = l2p.next;
            }
        }

        if(l1p != null){
            tail.next = l1p;
        }else {
            tail.next = l2p;
        }

        return result.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
